﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Intrinsics.Arm;
using System.Text;
using System.Threading.Tasks;

class Sol64
{

    public int MinPathSum(int[][] grid)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        int[][] dp = new int[m][];
        for (int i = 0; i < m; i++) { dp[i] = new int[n]; }


        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {


                Console.WriteLine("i:  "+i+"   j: "+j);
                if (i == 0 && j == 0)
                { dp[i][j] = grid[i][j];
                    continue;
                }

                if (i == 0)
                {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                }else if                 (j == 0)
                {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                }
                else
                {
                    dp[i][j] = Math.Min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
                }


                Console.WriteLine("dp[i][j]    "+ dp[i][j]);


            }
        }

        return dp[m - 1][n - 1];
    }
}
    class Program164
    {

        static void Main164(string[] args)
        {
            int m = 3;
            int n = 3;

            int[][] grid = new int[m][];
            grid[0] = new int[n];
            grid[0] = [1, 3, 1];
            grid[1] = [1, 5, 1];
            grid[2] = [4, 2, 1];
            Sol64 sol = new Sol64();
            int res = sol.MinPathSum(grid);
            Console.WriteLine(res);



        }


    }


